package main

func main() {

}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNode struct {
	Val  int
	Next *ListNode
}

// 迭代反转链表
func reverseList(head *ListNode) *ListNode {

	curNode := head
	var pre *ListNode
	for curNode != nil {
		tempNode := curNode.Next
		curNode.Next = pre
		pre = curNode
		curNode = tempNode
	}
	return curNode
}

// 递归反转链表
func reverseList2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	tmpNode := head
	newHead := reverseList2(head.Next)
	tmpNode.Next.Next = tmpNode
	tmpNode.Next = nil
	return newHead
}

// 从指定位置反转链表
func reverseList3(head *ListNode, left, right int) *ListNode {
	dummyNode := &ListNode{Val: -1}
	dummyNode.Next = head
	var pre *ListNode = dummyNode
	for i := 0; i < left-1; i++ {
		pre = pre.Next
	}
	cur := pre.Next
	for i := 0; i < right-left; i++ {
		next := cur.Next
		cur.Next = next.Next
		next.Next = pre.Next
		pre.Next = next
	}
	return dummyNode.Next
}

// 环形链表
func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	for slow, fast := head, head.Next; fast != nil && fast.Next != nil; slow, fast = slow.Next, fast.Next.Next {
		if slow == fast {
			return true
		}
	}
	return false
}
